import java.util.Arrays;

public class Solution673 {
    private int getMaxPathCount(int[][] dp){
        int maxPath = 0, maxPathCount = 0;
        for (int[] tmp:dp) {
            int tmpPath = tmp[0];
            int tmpCount = tmp[1];
            if(tmpPath > maxPath){
                maxPath = tmpPath;
                maxPathCount = tmpCount;
                continue;
            }
            if(tmpPath == maxPath){
                maxPathCount += tmpCount;
            }
        }
        return maxPathCount;
    }

    public int findNumberOfLIS(int[] nums) {
        int[][] dp = new int[nums.length][2];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1; // 0:最远步数 1：个数
            dp[i][1] = 1; // 0:最远步数 1：个数
        }
        for (int i = 1; i < dp.length; i++) {
            int iNum = nums[i];
            for (int j = 0; j < i; j++) {
                int jNum = nums[j];
                if(iNum > jNum){
                    int maxPath = dp[j][0] + 1;
                    if(maxPath > dp[i][0]){
                        dp[i][0] = maxPath;
                        dp[i][1] = dp[j][1];
                        continue;
                    }
                    if(maxPath == dp[i][0]){
                        dp[i][1] += dp[j][1];
                    }
                }
            }
        }
        return getMaxPathCount(dp);
    }

    public static void main(String[] args) {
        Solution673 s =new Solution673();
        System.out.println(s.findNumberOfLIS(new int[]{2,2,2,2,2}));
    }
}
